package interview.Sorting;

public class HeapSort {
	public static void BuildHeap(int num[]){
		for(int i = 1;i<num.length;i++){
			int cindex = i;
			int pindex ;
			if(cindex%2==0) pindex = (cindex - 2)/2;
			else pindex = (cindex - 1)/2;
				
			while(num[cindex]>num[pindex]){
				//System.out.println("swap elements:" + num[pindex]+"    "+ num[cindex]);
				Generic.swap(num, pindex, cindex);
				cindex = pindex;
				if(pindex%2==0) pindex = (pindex-2)/2;
				else pindex = (pindex-1)/2;
				if((cindex<0)||(pindex<0))break;
			}				
		}
	}
	public static void sort(int num[]){
		BuildHeap(num);
		System.out.println("Build Heap:");
		Generic.printArray(num);
		for(int i = num.length-1; i>=0 ; i--){
			Generic.swap(num, 0, i);
			int lindex, rindex,index=0;
			lindex = index+1;
			rindex = index+2;
			if((i==2)){
				if(num[index]>num[lindex])
					Generic.swap(num, lindex, index);
				break;
			}
			while((num[index]<num[rindex])||((num[index]<num[lindex])))
			{	if(num[lindex]>num[rindex]){ Generic.swap(num, index, lindex); index = lindex;}
				else {Generic.swap(num, index, rindex); index = rindex;}
				lindex = (2 * index) +1;
				rindex = (2 * index) + 2;
				if ((lindex>i-1) || (rindex>i-1)){
					if ((lindex>i-1) && (rindex>i-1)){
						break;
					}
					else if(rindex>i-1){
						if(num[index]<num[lindex])
							Generic.swap(num, lindex, index);
						break;
					}
					else{
						if(num[index]<num[rindex])
							Generic.swap(num, rindex, index);
						break;						
					}
				}				
			}
			System.out.println();
			Generic.printArray(num);
		}
		System.out.println();
		Generic.printArray(num);
	} 
}
